package pro.softzhang.algo.lc300;

/**
 * TODO 加练
 */
public class LC304_RangeSumQuery2DImmutable {
    public static void main(String[] args) {
        NumMatrix matrix = new NumMatrix(null);
        int sum = matrix.sumRegion(0, 0, 0, 0);
        System.out.println(sum);
    }

    static class NumMatrix {
        private int[][] sums;

        public NumMatrix(int[][] matrix) {
            if(matrix.length == 0 || matrix[0].length == 0) {
                return;
            }
            sums = new int[matrix.length + 1][matrix[0].length + 1];
            for (int i = 0; i < matrix.length; i++) {
                int rowSum = 0;
                for (int j = 0; j < matrix[0].length; j++){
                    rowSum += matrix[i][j];
                    sums[i + 1][j + 1] = sums[i][j + 1] + rowSum;
                }
            }
        }

        public int sumRegion(int row1, int col1, int row2, int col2) {
            return sums[row2 + 1][col2 + 1]
                    - sums[row1][col2 + 1]
                    - sums[row2 + 1][col1]
                    + sums[row1][col1];
        }
    }
}
